현대 프로세서는 다음과 같은 형태의 주소 지정 방식을 사용한다: 가상 주소 지정. 가상 메모리 (VM) 은 각 프로세스에게 고유하고 연속적인 선형 주소 공간.
1. 주소 지정의 진화
각각의 경우에 대해 물리 주소 지정 (그림 9.1), 프로세서는 물리 주소 (PA) 를 직접 DRAM으로 전달한다. 반면, 가상 주소 지정 (그림 9.2)에서는 프로세서가 가상 주소 (VA)를 생성하고, 이를 메모리 관리 유닛 (MMU) 이용하여 메모리에 접근하기 전에 물리 주소 (PA)로 변환한다.
2. 계층 구조 및 캐시
DRAM은 디스크 저장 장치에 대한 DRAM 캐시 역할을 한다. 디스크 지연 시간 때문에 시스템은 쓰기-백 정책을 사용한다. 번역 속도는 TLB 을 통해 TLB 인덱스 (TLBI) 를 사용하며, 예를 들어 PROT_WRITE와 같은 비트에 의해 보호된다. 큰 주소 공간 ($N = 2^n$)은 복잡한 세그먼트 및 입출력 장치용 운영체제 서비스.
main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>
QUESTION 1
[Fill in the blanks] Complete the following table for a Virtual Address Space where $N = 2^n$ and the largest address is $N-1$. Use units: $K=2^{10}, M=2^{20}, G=2^{30}, T=2^{40}, P=2^{50}, E=2^{60}$.
n=16: N=64K, Max=0xFFFF; n=32: N=4G, Max=0xFFFFFFFF; n=48: N=256T, Max=0xFFFFFFFFFFFF; n=64: N=16E, Max=0xFFFFFFFFFFFFFFFF
n=16: N=16K; n=32: N=32M; n=48: N=48G; n=64: N=64T
✅ Correct!
Correct. Virtual address space growth is exponential. $2^{16}=64K$, $2^{32}=4G$, $2^{48}=256T$, and $2^{64}=16E$.❌ Incorrect
Recall that $N = 2^n$. $2^{10}$ is 1K, $2^{20}$ is 1M, $2^{30}$ is 1G, etc.QUESTION 2
Why does the DRAM cache use a Write-back policy instead of Write-through?
To maintain Stack Discipline.
Due to the massive latency penalty of accessing disk storage.
To prevent internal fragmentation.
Because the L3 unified cache is 16-way associative.
✅ Correct!
Correct. Synchronizing with the disk on every write would be too slow, so updates are deferred until swapping occurs.❌ Incorrect
Disk access is roughly 100,000 times slower than DRAM; writing back only when necessary is vital.QUESTION 3
What happens if a process attempts to write to a page where the PTE has PROT_WRITE set to 0?
A General protection fault occurs.
The MMU performs Swapping automatically.
Deferred coalescing is triggered.
The Reference bit (A bit) is cleared.
✅ Correct!
Correct. The MMU hardware checks protection bits during address translation; violations trigger an exception (segfault/GPF).❌ Incorrect
Protection bits are enforced by hardware to ensure process isolation in the virtual address space.QUESTION 4
Which component is responsible for translating the Virtual Address to a Physical Address?
The L3 unified cache (8 MB, 16-way).
The Memory Management Unit (MMU).
The Rio Package.
The Buddy System Allocator.
✅ Correct!
Correct. The MMU is the hardware that performs the mapping using page tables and the TLB.❌ Incorrect
The MMU sits between the CPU and main memory specifically for this translation.QUESTION 5
What is the physical address (PA) if the MMU finds a mapping for a VA where VPN=0x0d and VPO=0x14, given PPN=0x0d?
PA = 0x354: PPN=0x0d, PPO=0x14
$PA = 0x140d$
$PA = 0x0001$
PA = 0x354: VPN=0x0d, VPO=0x14
✅ Correct!
Correct. PPO is identical to VPO. PA is the concatenation of PPN and PPO.❌ Incorrect
During translation, the offset (VPO) stays the same (becomes PPO), while the VPN is mapped to a PPN.Case Study: Advanced Heap Management & VM Translation
Optimizing Allocators and Address Translation Efficiency
You are designing a high-performance allocator for an Intel Core i7 system with a k-level page table hierarchy. The allocator uses a single global variable (heap_listp) and must minimize external fragmentation using Buddy System Allocation. You also need to modify the block structure to improve Peak memory utilization.
Q
1. Implement the 'find_fit' function for a simple implicit list allocator using first-fit logic. Your solution must account for Internal fragmentation and return NULL if no block is found.
Solution:
Implementation: static void *find_fit(size_t asize) { void *bp; /* Iterate through the heap starting from heap_listp */ for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { /* If block is not allocated and size is sufficient */ if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { return bp; } } return NULL; /* No fit found */ } This function searches the linear heap space, balancing search speed with memory utilization.
Implementation: static void *find_fit(size_t asize) { void *bp; /* Iterate through the heap starting from heap_listp */ for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { /* If block is not allocated and size is sufficient */ if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { return bp; } } return NULL; /* No fit found */ } This function searches the linear heap space, balancing search speed with memory utilization.
Q
2. Explain how to modify an allocator to remove boundary tags (footers) from allocated blocks. How does this affect Peak memory utilization and the mm_free(void *bp) logic?
Solution:
To remove footers in allocated blocks, we store an 'extra' bit in the header of the *next* block to indicate whether the *current* block is allocated. This allows us to reduce the minimum block size by one word, directly increasing Peak memory utilization by reducing internal fragmentation in small objects. However, mm_free and coalesce(bp) must now inspect the header of the next block to determine if the previous block can be merged, maintaining constant-time coalescing for free blocks (which still require footers).
To remove footers in allocated blocks, we store an 'extra' bit in the header of the *next* block to indicate whether the *current* block is allocated. This allows us to reduce the minimum block size by one word, directly increasing Peak memory utilization by reducing internal fragmentation in small objects. However, mm_free and coalesce(bp) must now inspect the header of the next block to determine if the previous block can be merged, maintaining constant-time coalescing for free blocks (which still require footers).
Q
3. Describe the 'Buddy System Allocation' process for a block of size 32 bytes at address xxx...x10000. How does it handle recursive splitting?
Solution:
The Buddy System finds a block of size $2^j$ where $k \le j \le m$. To allocate 32 bytes ($2^5$), if only a $2^7$ block is available, it splits into two $2^6$ buddies. One $2^6$ block is then split again into two $2^5$ buddies. One buddy at address xxx...x10000 is allocated, while its buddy (address xxx...x11000) remains free. This minimizes external fragmentation and allows for fast buddy-merging using bitwise address operations.
The Buddy System finds a block of size $2^j$ where $k \le j \le m$. To allocate 32 bytes ($2^5$), if only a $2^7$ block is available, it splits into two $2^6$ buddies. One $2^6$ block is then split again into two $2^5$ buddies. One buddy at address xxx...x10000 is allocated, while its buddy (address xxx...x11000) remains free. This minimizes external fragmentation and allows for fast buddy-merging using bitwise address operations.